package org.shj.algorithm;

/**
 * 给定 n 个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度都为1.
 * 若使用这样形状的容器集水，可以盛多少水量
 * 例：给出 0,1,0,2,1,0,1,3,2,1,2,1 ，则结果为 6
 * 图示见： collectRain.png
 *
 *
 * 解题思路：
 * 1. 最左L 和最右R 的两个方柱，不可能储水。
 * 2. 取 L 和 R 中较短的记为 X，与 X 相邻的记为 Y
 * 3. 若 Y >= X，则 Y 与不可能储水, 丢弃 X
 * 4. 若 Y < X，则 Y 储水量为 X - Y，丢弃 X
 * 5. 总之，无论如何，都会往中间靠一位，循环上面的，直至 L和R的位置重合
 *
 * @author Shen Huang Jian
 * @date 2019/6/2
 */
public class MaxCollect {

    static int sum = 0;

    public static void main(String[] args){
        int[] arr = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        calc(arr);
        System.out.println(sum);
    }

    private static void calc(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        int secHight = 0;
        while(left < right){
            if(arr[left] < arr[right]){
                secHight = arr[left] > secHight ? arr[left] : secHight;
                sum += secHight - arr[left];
                left++;
            }else{
                secHight = arr[right] > secHight ? arr[right] : secHight;
                sum += secHight - arr[right];
                right--;
            }
        }
        /*if(left == right){
            return;
        }
        int x = arr[left] >= arr[right] ? right : left;
        int y = arr[left] >= arr[right] ? (right-1) : (left+1);
        int increase = y-x;
        if(arr[y] >= arr[x]){
            if(arr[left] >= arr[right]){
                calc(arr, left, y);
            }else{
                calc(arr, y, right);
            }
        }else{
            while(arr[y] < arr[x]){
                sum += arr[x] - arr[y];
                y += increase;
            }
            if(arr[left] >= arr[right]){
                calc(arr, left, y);
            }else{
                calc(arr, y, right);
            }
        }*/

    }
}
